import java.util.*;

class Node {
    public int val;
    public List<Node> children;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, List<Node> _children) {
        val = _val;
        children = _children;
    }
};

/**
 * 429. N 叉树的层序遍历
 * https://leetcode.cn/problems/n-ary-tree-level-order-traversal/description/
 */
class Solution {
    public List<List<Integer>> levelOrder(Node root) {
        List<List<Integer>> ret = new ArrayList();
        if(root == null) return ret;
        Queue<Node> q = new LinkedList();

        q.add(root);

        while(!q.isEmpty()) {
            int sz = q.size();
            List<Integer> tmp = new ArrayList();//统计本层的节点信息
            for(int i = 0; i < sz; i++) {
                Node t = q.poll();
                tmp.add(t.val);
                for(Node child : t.children) {//让孩子入队
                    if(child != null) q.add(child);
                }
            }
            ret.add(tmp);
        }
        return ret;
    }
}

/**
 * 946. 验证栈序列
 * https://leetcode.cn/problems/validate-stack-sequences/description/
 */
////老师的
//class Solution {
//    public boolean validateStackSequences(int[] pushed, int[] popped) {
//        Stack<Integer> stack = new Stack();
//        int i = 0, n = pushed.length;
//        for(int x : pushed) {
//            stack.push(x);
//            while(!stack.empty() && stack.peek() == popped[i]) {
//                stack.pop();
//                i++;
//            }
//        }
//        return i == n;
//    }
//}
//自己写的
//class Solution {
//    public boolean validateStackSequences(int[] pushed, int[] popped) {
//        Stack<Integer> stack = new Stack();
//        int n = pushed.length, i = 0, j = 0;
//        while(j < n) {
//            //1、进栈
//            while (stack.empty() || popped[i] != stack.peek()) {
//                if(j >= n) break;
//                stack.push(pushed[j]);
//                j++;
//            }
//            //2、进栈的同时，判断是否要出栈
//            while (!stack.empty() && stack.peek() == popped[i]) {
//                stack.pop();
//                i++;
//            }
//        }
//        if(stack.empty() || i >= n) return true;
//        return false;
//    }
//}